#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define INF 0x3f3f3f3f

// 点结构
struct Point
{
    // 坐标
    int x, y;
    
    // 构造函数 
    Point(int x1, int y1):x(x1),y(y1) {}
};

// 用于按x递增排序
int cmpx(Point a, Point b)
{
    return a.x < b.x;
}

// 用于按y递增排序
int cmpy(Point a,Point b)
{
    return a.y < b.y;
}

// 求两个点之间的距离
double dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

double mindistance1(vector<Point>&p, int l, int r)	
{
    // 区间中只有一个点
    if(l >= r)	
        return INF;
    
    // 区间中只有两个点
    if(l+1==r)
        return dis(p[l], p[r]);
    
    // 求中点位置
    int mid=(l+r)/2;	
    
    // 左半部分最近点距离
    double d1 = mindistance1(p, l, mid);
    
    // 右半部分最近点距离
    double d2= mindistance1(p,mid+1,r);
    
    // 候选最近点距离
    double d = min(d1, d2);
    
    // 与中点x方向距离<d的点存放在p1中
    vector<Point> p1;
    for(int i=l; i<=r; i++)
        if(fabs(p[i].x-p[mid].x)<d)
            p1.push_back(p[i]);
    
    // p1中所有点按y递增排序
    sort(p1.begin(), p1.end(), cmpy);
    
    // 求最近点距离
    for(int i=0; i<p1.size(); i++)
        for(int j=i+1,k=0; k<7 && j<p1.size() && p1[j].y-p1[i].y<d; j++,k++)
            d = min(d, dis(p1[i], p1[j]));
    return d;
}

// 求p中最近点对距离
double mindistance(vector<Point> &p)
{
    // 全部点按x递增排序 
    sort(p.begin(), p.end(), cmpx);
    
    // 求坐标点个数
    int n = p.size();
    
    // 返回最近点对距离
    return mindistance1(p, 0, n-1);
}

int main()
{
    // 初始化10个坐标点
    vector<Point> p = { Point(4,10), Point(3,7), Point(9,7),
                        Point(3,4), Point(5,6), Point(5,4),
                        Point(6,3), Point(8,1), Point(3,0), Point(1,6)};
    // 求最近点距离
    printf("最近点对距离=%g\n", mindistance(p));
    return 0;
}

